package offer.zixing.chapter02;

/**
 * 乘积小于k的子数组
 *
 * 输入一个由正整数组成的数组和一个正整数k，请问数组中有多少个数字乘积小于k的连续子数组？
 * 例如输入数组[10, 5, 2, 6]，k的值为100，有8个子数组的所有数字的乘积小于100，
 * 它们分别是[10]、[5]、[2]、[6]、[10, 5]、[5, 2]、[2, 6]和[5, 2, 6]。
 */
public class Test009 {
    public static void main(String[] args) {
        System.out.println(numSubarrayProductLessThank(new int[]{10, 5, 2, 6}, 100));
    }

    public static int numSubarrayProductLessThank(int[] nums, int k) {
        long product = 1;
        int left = 0;
        int count = 0;
        for (int right = 0; right < nums.length; right++) {
            // 子数组值相乘
            product *= nums[right];
            // 左指针在右指针左边 且 乘积 > 目标值
            while (left <= right && product >= k) {
                // 将最左值在乘积累计中移除，并将左指针右移
                product /= nums[left++];
            }
            // 每次产生  right - left + 1 个子数组
            // 1 + 2 + 2 + 3 = 8
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }
}
